//有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
//给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
public class Solution {
    public int findKth (int[] a, int n, int K) {
        return sort(a,0,n-1,K);
}
public int sort(int[] a, int left,int right,int K) {
        if(left == right){
            return a[left];
        }
        int pivotIndex = partition(a,left,right);
        int rank = right - pivotIndex+1;
        if (rank == K) {
            return a[pivotIndex];
        } else if (rank > K) {
            // 第 K 大的元素在分区点的右边
            return sort(a, pivotIndex + 1, right, K);
        } else {
            // 第 K 大的元素在分区点的左边
            return sort(a, left, pivotIndex - 1, K - rank);
        }
        
}
    public int partition(int[] a,int left,int right){
        // write code here
        int i = left;
        int j = right;
        int pivot = a[left];
        while(i < j){
            while(i < j && a[j] > pivot){
                j--;
            }
            a[i]= a[j];
            while(i < j && a[i] < pivot){
                i++;
            }
            a[j] = a[i];
        }
        a[i] = pivot;
       return i;
    }
}
